package 斐波那契数;

import java.util.Arrays;

/**
 * createTime: 2025/4/28 23:25
 * description:
 *
 * @author AirMan
 */
public class Solution {
    public int fib(int n) {
        // dynamic-programming 五部曲
        // ① 确定dp数组以及下标含义
        // ② 确定递推公式
        // ③ dp数组如何初始化
        // ④ 确定遍历顺序
        // ⑤ 举例推到dp数组

        // ① dp[i]的定义为：第i个数的斐波那契数值是dp[i]
        // ② dp[i] = dp[i - 1] + dp[i - 2]
        // ③ dp[0] = 0; dp[1] = 1;
        // ④ 从前到后遍历
        // ⑤ 如果 n == 10 ，那么打印为：0 1 1 2 3 5 8 13 21 34 55

        if (n == 0 || n == 1)
            return n;
        // dp[i]的定义为：第i个数的斐波那契数值是dp[i]
        int[] dp = new int[n+1];

        // 初始化
        dp[0] = 0;
        dp[1] = 1;
//        System.out.println(Arrays.toString(dp));
        // 从前到后遍历
        for (int i = 2; i <= n; i++) {
            // 递推公式: dp[i] = dp[i - 1] + dp[i - 2]
            dp[i] = dp[i - 1] + dp[i - 2];
            // 举例推到dp数组
//            System.out.println(Arrays.toString(dp));
        }

        return dp[n];
    }

}
